package Z代码随想录.数组;

public class SearchInsertLocation {

    // 题目：搜索插入位置
    // 考虑用二分查找
    public int searchInsert(int[] nums, int target) {
        // 如果 target 比 nums[0]小，则返回 0 下标
        if(target < nums[0]){
            return 0;
        }
        // 如果target 比 nums[nums.length-1] 大， 则返回 nums.length 下标
        if(target > nums[nums.length-1]){
            return nums.length;
        }
        int left = 0;
        int right = nums.length-1;
        while(left <= right){
            int mid = left + ((right - left)>>1);
            if(nums[mid] == target){
                return mid;
            }else if (nums[mid] > target){   // 中间值比目标值大，则往左边找
                right = mid - 1;
            }else{                           // 中间值比目标值小，则往右边找
                left = mid + 1;
            }
        }
        // 此时说明没找到，没找的情况就是  right < left，此时无论 是 比当前mid大，还是比当前 mid 小，left的位置就是插入位置
        return left;
    }
}
